package algorithm.sort.n2;

/**
 * @author: Oliver
 * @time: 2020/5/31/10:28
 * <p>
 * 选择排序 N^2
 * 选择排序 如果是按照从大到小排序，每次选择当前位置元素 i  和 [i+1,size)中元素最大的元素进行交换位置
 */
public class SelectionSort {
    public static void main(String[] args) {
        // 测试排序算法辅助函数
        int N = 20000;
        Integer[] arr = HelperTest.generateRandomArray(N, 0, 100000);
        selectionSort(arr, arr.length);
        HelperTest.printArray(arr);

        return;
    }

    public static void selectionSort(Comparable[] arr, int n) {
        for (int i = 0; i < n; i++) {
            int index = i;
            // 寻找[i+1, n)区间里的最大元素的索引
            for (int j = i + 1; j < n; j++) {
                if (arr[index].compareTo(arr[j]) < 0) {
                    index = j;
                }
            }

            //进行交换两个位置
            if (index != i) {
                swap(arr, index, i);
            }
        }
    }

    public static void swap(Object[] arr, int i, int j) {
        Object temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
